package com.graph;

import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.Stack;

public class BreadthFirstPath {

    private Graph g;
    private int[] pathTo;
    private final int s;
    private boolean[] marked;
    public BreadthFirstPath(Graph g, int s) {
        this.s = s;
        this.g = g;
        pathTo = new int[g.V()];
        marked = new boolean[g.V()];
        bfs(g, s);
    }

    public void bfs(Graph g, int s) {
        Queue<Integer> queue = new Queue<>();
        queue.enqueue(s);
        while (!queue.isEmpty()) {
            int v = queue.dequeue();
            for (int w : g.adj(v)) {
                if (!marked[w]) {
                    marked[w] = true;
                    pathTo[w] = v;
                    queue.enqueue(w);
                }
            }
        }
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v) {
        Stack<Integer> stack = new Stack<>();

        for (int i = v; i != s ; i = pathTo[i]) {
            stack.push(i);
        }
        stack.push(s);
        return stack;
    }
}
